/*
 * 用于生成CDG
 * 创建对象之后用addEdge建图
 * 之后执行init和getCDG即可获得CDG
 * 复杂度n
*/
import {Edge, Graph} from './graph'
import {FDT} from './fdt'

export class CDG{
    N:number;
    in:number[];
    v:Array<number>[];
    end:number;
    
    constructor(N:number){
        this.N = N;
        this.end = N+1;
        this.in = new Array<number>(N+10).fill(0);
        this.v = new Array<Array<number>>(N+10);
        for(let i=0;i<=N+9;i++){
            this.v[i]=new Array<number>;
        }
    }
    addEdge(u:number,v:number){
        // console.log(u);
        this.v[u].push(v);
        this.in[v]++;
    }
    init(){
        for(let i=0;i<=this.N-1;i++){
            if(this.in[i]==0){
                this.addEdge(this.end,i);
            }
        }
    }
}
export class CDGGEN{
    N:number;
    st:number;//起始节点
    ed:number;//结束节点
    cfg:Graph;
    cfg_d:Graph;
    cdg:CDG;
    fdt:FDT;

    constructor(N:number,st:number,ed:number){
        this.N = N;
        this.st = st;
        this.ed = ed;
        this.cfg = new Graph(N,st,ed);
        this.cfg_d = new Graph(N,ed,st);
        this.cdg = new CDG(N);
        this.fdt = new FDT(N,ed);
    }
    addEdge(u:number,v:number){
        this.cfg.addEdge(u,v);
        this.cfg_d.addEdge(v,u);
    }
    init(){
        this.cfg_d.init();
        this.fdt = this.cfg_d.getFDT();
        this.cfg.edge.forEach((e)=>{
            let a:number = e.u;
            let b:number = e.v;
            if(!this.fdt.isGrand(b,a)){
                let now:number = b;
                while(now!=this.fdt.fa[a]){
                    this.cdg.addEdge(a,now);
                    now = this.fdt.fa[now];
                }
            }
        });
        this.cdg.init();
    }
    getCDG():CDG{
        return this.cdg;
    }
}